Hint

In Prolog, we will simply store this table as facts in the knowledge base:

lc(np,s).
lc(pn,s).
lc(det,np).
lc(pn,np).
lc(det,s).
lc(iv,vp).
lc(tv,vp).

lc(X,X). Put each case.

Now, we can check every time that we choose a rule whether it makes sense to use this rule given the top-down information about the category that we are trying to recognize.

So, every time we decided on a category for a word, we first look into the left-corner table to check whether the category of the word can appear at the left corner of the constituent we are working on:

leftcorner_recognize(Cat,[Word|StringIn],StringOut) :-
lex(Word,WCat),
lc(WCat,Cat),
complete(Cat,WCat,StringIn,StringOut).

Similarly, we check that the left-hand sides of the rules we are using can appear as the left corner of the category we are building:

complete(Cat,SubCat,StringIn,StringOut) :-
LHS ---> [SubCat|Cats],
lc(LHS,Cat),
matches(Cats,StringIn,String1),
complete2(Cat,LHS,String1,StringOut).

The other clause of complete is unchanged.

Now, go back to the example and check what happens. In step four, where the previous version of the algorithm made the mistake, this new version would check whether lc(TV,N) is true. Since this is not the case, it would immediately backtrack and find the second possibility for plant in the lexicon.

Back to lab 2.